package sorting;

/**
 * Bubble Sort
 * 
 * i=0
 * [12, 3 , 4, 9, 0, 2, -1, 5]
 * [12, 3 , 4, 9, 0, -1, 2, 5]
 * [12, 3 , 4, 9, -1, 0, 2, 5]
 * [12, 3 , 4, -1, 9, 0, 2, 5]
 * [12, 3 , -1, 4, 9, 0, 2, 5]
 * [12, -1 , 3, 4, 9, 0, 2, 5]
 * [-1, 12 , 3, 4, 9, 0, 2, 5]
 * 
 * i=1
 * [-1, 12 , 3, 4, 9, 0, 2, 5]
 * [-1, 12 , 3, 4, 0, 9, 2, 5]
 * [-1, 12 , 3, 0, 4, 9, 2, 5]
 * [-1, 12 , 0, 3, 4, 9, 2, 5]
 * [-1, 0 , 12, 3, 4, 9, 2, 5]
 * 
 * ...
 * 
 * @author SamuelSantos
 *
 * @param <T>
 */
public class BubbleSort<T extends Comparable<T>> implements Sorting <T> {

	@Override
	public void sort(T[] array) {
		sort(array, 0, array.length);
	}

	private void sort(T[] array, int left, int right){
		for (int i = left+ 1; i < right; i++){
			for (int j = right -1; j >= i; j-- ){
				if (less(array, j-1, j)){
					Util.swap(array, j-1, j);
				}
			}
		}
	}
	
	 private boolean less(T[] array, int x, int y){
         return array[x].compareTo(array[y]) > 0;
	 }
	 
}
